#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
class Solution 
{
    vector<int> res;
public:
    vector<int> sortArray(vector<int>& nums) {
        //return ShellSort(nums);
        //srand(time(nullptr));
        //return QuickSort(nums);
        //return MergeSort(nums);
        //return HeapSort(nums);
        return CountSort(nums);
    }
    vector<int> CountSort(vector<int>& nums)
    {
        map<int,int> hash;
        for(auto e:nums)
            hash[e]++;
        for(auto it:hash)
        {
            while(it.second != 0)
            {    
                res.push_back(it.first);
                it.second--;
            }
        }
        return res;
    }
    void AdjustDown(vector<int>& nums, int parent, int n)
    {
        int child = parent * 2 + 1;
        while(child < n)
        {
            if(child + 1 < n && nums[child] < nums[child + 1])
                child += 1;
            if(nums[parent] < nums[child])
            {
                swap(nums[parent], nums[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else break;
        }
    }
    vector<int>& HeapSort(vector<int>& nums)
    {
        int n = nums.size();
        for(int i = (n - 2) / 2; i >=0; i--)
            AdjustDown(nums, i, n);
        int end = n - 1;
        while(end >= 1)
        {
            swap(nums[end], nums[0]);
            AdjustDown(nums, 0, end);
            end--;
        }
        return nums;
    }
    vector<int>& MergeSort(vector<int>& nums)
    {
        int n = nums.size();
        res.resize(n,0);
        _Merge(nums, 0, n - 1);
        return nums;
    }
    void _Merge(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        int mid = (right + left) >> 1;
        _Merge(nums, left, mid);
        _Merge(nums, mid + 1, right);
        int first1 = left;
        int last1 = mid;
        int first2 = mid + 1;
        int last2 = right;
        int cur = left;
        while(first1 <= last1 && first2 <= last2)
            res[cur++] = nums[first1] < nums[first2] ? nums[first1++] : nums[first2++];
        while(first1 <= last1) res[cur++] = nums[first1++];
        while(first2 <= last2) res[cur++] = nums[first2++];
        for(cur = left; cur <= right; cur++)
            nums[cur] = res[cur];
    }
    vector<int>& ShellSort(vector<int>& nums)
    {
        int n = nums.size();
        int gap = n;
        while(gap > 1)
        {
            gap /= 2;
            for(int i = 0; i < n - gap; i++)
            {
                int left = i;
                int tmp = nums[i + gap];
                while(left >= 0)
                {
                    if(tmp < nums[left])
                    {
                        nums[left + gap] = nums[left];
                        left -= gap;
                    }
                    else break;
                }
                nums[left + gap] = tmp;
            }
        }
        return nums;
    }
    vector<int>& QuickSort(vector<int>& nums)
    {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        _Quick(nums, left, right);
        return nums;
    }
    void _Quick(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        int l = left - 1;
        int r = right + 1;
        int cur = left;
        int mid = nums[rand() % (right - left + 1) + left];
        while(cur < r)
        {
            if(nums[cur] < mid) swap(nums[cur++], nums[++l]);
            else if(nums[cur] == mid) cur++;
            else swap(nums[cur], nums[--r]);
        }
        _Quick(nums, left, l);
        _Quick(nums, r, right);
    }
};